//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：["()"]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 8 
// 
// Related Topics 字符串 回溯算法 
// 👍 1593 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List<String> result=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return result;
        }
        StringBuilder sb = new StringBuilder();
        dfs(n,n,sb);
        return result;

    }
    public void dfs(int a,int b,StringBuilder sb){
        if(a==0&&b==0){//添加结果并回溯
            result.add(sb.toString());
            return;
        }
        if(a>b)//枝剪 因为左边要严格小于右边才那才能保证括号配对
            return;
        if(a>0)//先深度优先搜索右边
        {
            dfs(a-1,b,sb.append("("));
            sb.deleteCharAt(sb.length() - 1);//因为下一个分支也要使用同一个StringBuilder 所以以需要把当前添加的括号删除
        }                                      //String不影响原来的字符串结构 但是stringbuilder会影响原来的字符串结构
        if (b > 0) {//深度优先搜索左边
            dfs(a,b-1,sb.append(")"));
            sb.deleteCharAt(sb.length() - 1);
        }

    }
}
//leetcode submit region end(Prohibit modification and deletion)
